Leetcode-Climbing Stairs

发表于 | 分类于 |

Climbing Stairs

爬梯子问题。给定一个n级台阶，每次可以走一个台阶或者两个台阶，一共有多少种走法？
Description

解题思路：
很常见的一种递推题型，要求n级台阶的走法，即可以分解为求n-1级台阶加上n-2级台阶的走法，climbNum[n]=climbNum[n-1]+climbNum[n-2]。所以问题实质上就是求解斐波那契数列。但由于采用递推方式会产生大量重复的计算，因此使用动态规划自底向上的进行计算，其中我们使用一个数组用于保存每步产生的结果。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution(object):
    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n<=2:
            return n
        climbNum = [1,1,2]
        for i in range(3,n+1):
            climbNum.append(climbNum[i-1] + climbNum[i-2])
        return climbNum[n]